本篇同步發布於Blog:[解題] LeetCode - 238 Product of Array Except Self

平台：

LeetCode

題號：

238 - Product of Array Except Self

題目連結：

https://leetcode.com/problems/product-of-array-except-self/

題目說明：

        輸入1個陣列nums，需產生新的陣列output，而新的陣列的值output[i] 是原本陣列其他元素相乘但不包含相乘nums[i]的結果。題目要求時間複雜度為O(n)且不能用額外的計算空間。

        比如範例輸入的[1, 2, 3 ,4]，答案是[2 * 3 * 4, 1 * 3 * 4, 1 * 2 * 4, 1 * 2 * 3] = [24, 12, 8, 6]

解題方法：

   　可以先用數學代數分析題目，假設陣列的值是 [x, y, z, w]，第一次我們從索引值 i = 0 往上遞增，先建立一版不包含當前nums[i]的相乘，之後再從i = n - 1往下遞減，乘上當前nums[i+1]的解。

1. 先從i = 0 到 n-1，output變化為 [1] => [1, x * 1] => [1, x, y * x] => [1, x, yx, z * xy] = [1, x, yx, zxy]
2. 再從 i = n -1 到 ，output變化為[1, x, yx, zxy * 1] => [1, x, yx * w, zxy] => [1, x * zw, yxw, zxy] =>  [1 * zwy, xzw, yxw, zxy] = [zwy, xzw, yxw, zxy]

最終答案是[zwy, xzw, yxw, zxy]，每個元素都不包含原本nums[i]的值

難度為Medium

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        
        ans[0] = 1;
        for(int i = 1; i < n;++i){
            ans[i] = nums[i-1] * ans[i-1];
        }
        
        int R = 1;
        for(int i = n - 1;i >= 0;--i){
            ans[i] = ans[i] * R;
            R *= nums[i];
        }
        
        return ans;
    }
};

int main() {
	vector<int> nums{1,2,3,4};
	Solution sol;
	vector<int> ans = sol.productExceptSelf(nums);
	for(int num : ans){
		cout << " " << num;
	}
	cout << endl;
	return 0;
}

using System;

namespace LeetCode238
{
	public class Program
	{
		public class Solution {
			public int[] ProductExceptSelf(int[] nums) {
				int n = nums.Length;
				int[] ans = new int[n];

				ans[0] = 1;
				for(int i = 1; i < n;++i){
					ans[i] = nums[i-1] * ans[i-1];
				}

				int R = 1;
				for(int i = n - 1;i >= 0;--i){
					ans[i] = ans[i] * R;
					R *= nums[i];
				}

				return ans;
			}
		}

		public static void Main()
		{
			Solution sol = new Solution();
			int[] nums = new int[]{1,2,3,4};
			int[] ans = sol.ProductExceptSelf(nums);
			foreach(int num in ans)
			{
				Console.Write(" " + num);
			}
			Console.WriteLine("");
			Console.Read();
		}
	}
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/200-299/238.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/200-299/238.cs